package com.wubotao.algorithm;

import java.util.Arrays;

public class QuickSort {

	private static int getMiddle(int[] list, int low, int high) {
		int tmp = list[low]; // assume the first is the middle
		while (low < high) {
			while (low < high && list[high] >= tmp) {
				high--;
			}
			list[low] = list[high]; // move the smaller to the left
			while (low < high && list[low] <= tmp) {
				low++;
			}
			list[high] = list[low]; // move the larger to the right
		}
		list[low] = tmp; 
		return low; // return the index of the middle
	}

	private static void qsort(int[] list, int low, int high) {
		if (low < high) {
			int middle = getMiddle(list, low, high); // split the array into two parts
			qsort(list, low, middle - 1); // sort the numbers smaller than the middle
			qsort(list, middle + 1, high); // sort the numbers larger than the middle
		}
	}

	public static void quick(int[] array) {
		if (array.length > 0) { 
			qsort(array, 0, array.length - 1);
		}
	}

	public static void main(String[] args) {
		int[] array = { 3, 6, 2, 5, 9, 1, 8 };
		quick(array);
		System.out.println(Arrays.toString(array));
	}
}
